import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author 03010570
 * @date 2020/07/08
 * describe:    LeetCode : 剑指Offer 03、数组中重复的数字  https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
 */
public class LeetCode_sword_offer_03 {
    public static void main(String[] args) {
        int[] ints = {2, 3, 1, 0, 2, 5, 3};
        System.out.println(findRepeatNumber3(ints));
    }

    /**
     *  先排序，后比对
     *  时间复杂度：O(NlogN)  严格来说是 O(NlogN + N)
     *  空间复杂度：O(1)
     * @param nums
     * @return
     */
    public static int findRepeatNumber3(int[] nums) {
        Arrays.sort(nums);
        for(int i =1;i<nums.length;i++){
            if(nums[i] == nums[i-1]){
                return nums[i];
            }
        }
        return 0;
    }

        /**
         * 原地排序，nums[i] 应该在 i 的位置，否则 nums[i] = nums[nums[i]] ,交换
         * 时间复杂度 ：O(N)
         * 时间复杂度 ：O(1)
         *
         * @param nums
         * @return
         */
    public static int findRepeatNumber2(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i) {
                if (nums[i] == nums[nums[i]]) {
                    return nums[i];
                }
                // 交换
                int temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
        }
        return 0;
    }

    /**
     * 时间复杂度 ：O(N)
     * 空间复杂度 ：O(N) HashSet
     *
     * @param nums
     * @return
     */
    public static int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return nums[i];
            }
            set.add(nums[i]);
        }
        return 0;
    }
}
